\documentclass{beamer}
\usepackage{multirow}
\usepackage{ctex}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{multicol}
\usetheme{Madrid}

\author{uncle-lu}
\title{关于求解多项式算法与进制转换算法的探究报告}
%\subtitle[sbt]{副标题}
\institute{乌鲁木齐市第一中学}
\date{\today}


\begin{document}

\frame{\titlepage}

\begin{frame}
	\frametitle{说在前面的话}
	
	\begin{itemize}
			\pause
		\item 很荣幸给各位巨佬们分享本菜鸡会的一些没用的东西．
			\pause
		\item 我和书上讲的有些差别.因为我觉得书上写的好丑.不适合学习.
			\pause
		\item 听说这节课之前是自习课.那我们讲快一点.
			\pause
		\item 希望不要有偷偷学习的同学.当然睡觉也不是很好.
	\end{itemize}
\end{frame}

\begin{frame}

\begin{multicols}{2}
	\tableofcontents
\end{multicols}

\end{frame}

\section{自然语言与程序语言}

\begin{frame}
	\frametitle{自然语言与程序语言}

	我们发现我们在求解问题或者描述事情的时候.是很有逻辑性的.然而我们的程序语言就是将这种逻辑性.通过更简单的标记.来记录.
\end{frame}

\section{求解多项式}

\subsection{这是一个什么样的模型}

\begin{frame}
	\frametitle{问题}

	我们给出任意一个多项式.

	\[f(x) = a_n x^{n} + a_{n-1} x^{n-1} + \dots + a_{1} x^{1} + a_{0} \]

	给出任意$x$值.让你求出所对应的$f(x)$

\end{frame}

\subsection{朴素算法1}

\begin{frame}
	\frametitle{朴素算法1}

	正如书上讲的那样.
	
	对于一些没头的人的计算方式会将各项依次计算.之后求和.

	你会发现时间复杂度为\(O(\frac{(1+n-1)*(n-1)}{2})\)

	\pause

	显然的发现.

	随着$n$的变大.时间复杂度会平方级上升.

	\pause

	所以这是一个平方级的算法.

\end{frame}

\subsubsection{代码实现}

\begin{frame}
	\frametitle{算法实现}
%scriptsize
	\begin{scriptsize}
		\begin{block}{BASIC}
			INPUT "n=";n

			INPUT "x=";x

			i=n

			ans=0

			WHILE i>=0

			\quad	INPUT " $a_i$ = ";a

			\quad	k=1

			\quad sum=1

			\quad			WHILE k<=i

			\quad\quad			sum=sum*x

			\quad\quad	k=k+1

			\quad	WEND

			\quad ans=ans+a*sum

			\quad				i=i-1

			WEND

			PRINT ans

			END
		\end{block}
	\end{scriptsize}

\end{frame}

\subsection{朴素算法2}

\begin{frame}
	\frametitle{朴素算法2}

	在算法1中.我们重复计算了很多次$x^k$.

	\pause

	我们如何优化这种做法.

	\pause

	显然我们可以记下来我们之前算过的$x^{k-1}$之后就可以计算出$x^{k}$

	这是很显然的.

	\pause

	显然发现.

	经过如此简单的处理.

	我们得出了一个$O(n)$复杂度的算法.

\end{frame}

\subsubsection{代码实现}

\begin{frame}
	\frametitle{代码实现}
	\begin{scriptsize}
		\begin{block}{BASIC}
			INPUT "n=";n

			INPUT "x=";x

			i=1

			k=1

			WHILE i<=n

			\quad k=k*x

			\quad i=i+1

			WEND

			ans=0

			WHILE i>=0

			\quad	INPUT " $a_i$ = ";a

			\quad	ans=ans+a*k

			\quad   k=k/x

			\quad	i=i-1

			WEND

			PRINT ans

			END
		\end{block}
	\end{scriptsize}

\end{frame}

\subsection{秦九韶算法}

\begin{frame}
	\frametitle{秦九韶算法}

	但是我们每次还是得去计算这个$x^{k}$.

	我们还可以怎么优化?

	\pause

	我们可以通过提取公因式.来达到在运算上降幂的效果.

	\[ f(x)=(\dots(a_n x + a_{n-1}) x + a_{n-2})x+\dots)x+a_0\]

	我们就不需要去考虑这个$x^{k}$

	\pause

	所以我们每次只需要循环处理$v_{k} = v_{k-1} x + a_{n-k}$即可.

	\pause

	但是我们发现这个算法还是一个$O(n)$的一个线性算法.

\end{frame}

\subsubsection{程序框图}

\begin{frame}
	\frametitle{程序框图}

	\centering
	\includegraphics[width=0.3\textwidth]{a.jpg}

\end{frame}

\subsubsection{代码实现}

\begin{frame}
	\frametitle{代码实现}

	\begin{small}
		\begin{block}{BASIC}
			INPUT " n = " ;n\\
			INPUT " x = " ;x\\
			ans=0\\
			i=n\\
			WHILE i>=0\\
			\quad INPUT " $a_i$ = " ; $a_i$\\
			\quad ans=ans*x+$a_i$\\
			\quad i=i-1\\
			WEND\\
			PRINT ans\\
			END
		\end{block}
	\end{small}

\end{frame}

\subsection{关于线性复杂度的讨论}

\begin{frame}
	\frametitle{线性复杂度}

	有心的同学可能已经发现.

	我们朴素算法2与秦九韶算法在时间复杂度上均为$O(n)$.

	它们到底有什么区别?

	\pause

	常数操作的不同.

	\pause

	在计算机中.大型算法常数操作是可以忽略的.我们发现我们朴素算法2要比秦九韶算法多处理一个$x_k$.

	那么这就多了一个常数操作.

	当$n$达到很大很大很大很大的值的时候.常数操作的多少才会体现出来.

	当然如果手算.立马就体现出来差别了.(逃)

\end{frame}

\section{进制转化}

\subsection{十进制转k进制}

\begin{frame}
	\frametitle{问题}

	给出一个十进制数.我们将它转化成k进制.

\end{frame}

\subsubsection{程序框图}

\begin{frame}
	\frametitle{流程图}

	\centering
	\includegraphics[width=0.3\textwidth]{b.jpg}

\end{frame}

\subsubsection{代码实现}

\begin{frame}
	\frametitle{代码实现}

	\begin{small}
		\begin{block}{BASIC}
			INPUT "a,k,n=";a,k,n

			b=0

			i=1

			t=a\quad MOD\quad 10

			DO

			\quad b=b+t*k\^{}(i-1)

			\quad a=a$\backslash$10

			\quad t=a\quad MOD\quad 10

			\quad i=i+1

			LOOP UNTIL i>n

			PRINT b

			END
		\end{block}
	\end{small}

\end{frame}

\subsection{k进制转十进制}

\begin{frame}
	\frametitle{问题?}
	一个k进制数转十进制.
\end{frame}

\subsubsection{程序框图}

\begin{frame}
	\frametitle{程序框图}
	
\end{frame}

\subsubsection{代码实现}
\begin{frame}
	\frametitle{代码实现}

\end{frame}

\begin{frame}
	
	\Huge
	Thanks.

	主讲人:uncle-lu

\end{frame}

\end{document}
